package code;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class DNA {
	
//	private static int[] set=new int[1048576+1];
//	private static HashSet<Integer> mark=new HashSet<Integer>();
	public List<String> findRepeatedDnaSequences(String s) {
		 int i,j;
		 StringBuilder sb=new StringBuilder(s);
		 List<String> list=new LinkedList<String>();
		 HashMap<Integer, Boolean> map=new HashMap<Integer,Boolean>();
		 for(i=0;i<sb.length()-9;i++){
			 int x=0;
			 String sub=s.substring(i, i+10);
			 for(j=0;j<10;j++){
				 x<<=2;
				 int t=CtoI(sb.charAt(i+j));
				 x+=t;
			 }
			 if(map.containsKey(x)){
				 if(!map.get(x))	list.add(sub);
				 map.put(x, true);
			 }
			 else{
				 map.put(x, false);
			 }
		 }
		 return list;
	}
	public int CtoI(char c){
		int ans=0;
		switch(c){
			case 'A':ans=0;break;
			case 'C':ans=1;break;
			case 'T':ans=2;break;
			case 'G':ans=3;break;
			default:
				break;
		}
		return ans;
	}
	public static void main(String[] args){
		DNA dna=new DNA();
		String p="AAAAAAAAAAAA";
		List<String> list=dna.findRepeatedDnaSequences(p);
		for(int i=0;i<list.size();i++){
			System.out.println(list.get(i));
		}
	}
}

